ECC can check and correct messages having errors by adding some redundant information. The errors may be incurred during transmission from a source to a receiver or due to defects of a storage device. For storage devices, ECC has been widely adopted to increase the reliability of data access and hence reduce the manufacturing costs. As increase of bit density and multiple-layers manufacturing processes of flash devices, the ECC plays a more and more important role. However, in order to have benefits from ECC, time of encoding and decoding processes will significantly reduce data access time.
To encode messages, one should feed the messages into an encoder provided with an adopted ECC and store an encoded data into a flash memory. Conventionally, in order to reduce waiting time, the messages will be bypassed to flash memory until the parity bits have been generated as shown in FIG. 1. Thus, the parity bits should be appended to the end of the messages in the flash memory as shown in FIG. 2.
Conventionally, to decode the data stored in the flash memory, the data fed into the ECC decoder should be with the same order as encoded data. The decoding process is shown in FIG. 2 as well. However, the decoding procedure cannot be started until the decoder receives the parity part. Besides, the length of buffer for data temporary storage also needs to be enlarged.
A Low-Density Parity Check (LDPC) code is an ECC that may be used in the transmission of information through a noisy communications channel, with or without memory. LDPC codes may be represented by many different types of parity check matrices. The structure of an LDPC code's parity check matrix may be, for example, random, cyclic, or quasi-cyclic. LDPC codes defined by quasi-cyclic parity check matrices are particularly common and computationally efficient. These codes are known as Quasi-Cyclic Low-Density Parity Check (QC-LDPC) codes.
A parity check matrix representative of a specified LDPC code may correspond to a bi-partite graph with check nodes and variable nodes. An LDPC decoder may decode received codewords using an iterative message passing algorithm. Each iteration or sub-iteration includes two updating steps involving the variable nodes and check nodes. In the first updating step, messages may be passed from some check nodes to some variable nodes. In the second updating step, messages may be passed from some variable nodes to some check nodes.
A LDPC decoder may perform the updating steps in accordance with a layered decoding process. In the decoding process, only those variable nodes necessary for updating a particular check node may be updated or only those check nodes necessary for updating a particular variable node may be updated.
A layered LDPC decoder may be used to decode QC-LDPC codes. For a QC-LDPC code with a quasi-cyclic parity check matrix, it is featured that it is consisted of circular sub-matrices (circulants). Since each circulant represents a connection between a check node and a variable node, if circulants in the first layer can be processes first and leave zero sub-matrices behind, decoding process can be speeded up due to less waiting time. Therefore, a data format based on the technique and a parity check matrix for forming that data format are desired so that throughput of the decoder can be increased and input buffer can be reduced.